This invention relates generally to semiconductor memories and in particular to a memory, known as a content addressable memory, in which the data is accessed and modified based upon the content of the stored data.
A content addressable memory (CAM) semiconductor device is a well known device which permits the contents of the memory to be searched and matched instead of having to specify one or more particular memory location(s) in order to retrieve data from the memory. A CAM may be used to accelerate any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. A CAM provides a performance advantage over conventional memory devices with conventional memory search algorithms, such as binary or tree-based searches, by comparing the desired information against the entire list of entries simultaneously, giving an order-of-magnitude reduction in the search time. For example, a binary search through a database of 1000 entries may take ten separate search steps whereas a CAM device with 1000 entries may be searched in a single operation resulting in a search which takes ten times less time. One example of an application in which CAM devices are often used is to store a routing table for high speed switching systems which need to rapidly search the routing table to look for a matching destination address so that a data packet may be routed to the appropriate destination address.
To better understand a CAM and its operation, the CAM structure and operation may be compared to conventional well-known random access memory (RAM) devices. A RAM device is an integrated circuit that temporarily stores data in an array of memory cells. In the RAM device, each stored piece of data may be accessed independently of any other piece of data. The data in a RAM is stored at a particular location called an address so that any piece of data in the RAM may be accessed by indicating the address at which the data is located. The RAM devices are often used for memory of a computer. Typical RAM devices may be organized as 262,144 memory locations (commonly called 256K) by four bits wide, or 1,048,576 memory locations (commonly called 1 Megabyte) by eight bits wide, but other different organizations also exist.
Typical RAM devices are composed of an array of memory cells wherein each memory cell may store a bit of information. Each memory cell may have one or more transistors depending on the type of RAM which may include a static RAM (SRAM) or a dynamic RAM (DRAM). A typical complementary metal on silicon (CMOS) implemented SRAM may have six transistors per memory cell in which four of the transistors are cross-coupled to store the state of the bit, and two transistors are used to alter or read out the state of the bit. For a SRAM, the state of the bit remains at one level or the other until deliberately changed or power is removed. DRAMs, on the other hand, have a dynamic storage unit which typically may include a single transistor and a capacitor which stores the bit information. During a read, the charge on the capacitor is drained to the bit line, requiring a rewrite of the bit, called a restore operation. Additionally, because the DRAM capacitor is not perfect, it loses charge over time, and needs to have its charge refreshed at regular intervals. Thus, dynamic memories are accompanied by controller circuits to rewrite the bit and refresh the stored charge on a regular basis.
A content addressable memory (CAM) device is organized differently from typical SRAM or DRAM devices. In particular, data in a CAM is stored in memory locations in a somewhat random fashion. The memory locations may be selected by an address bus or the data can be written directly into the first empty memory location because every location has a pair of special status bits that keep track of whether the location has valid information in it or is empty and therefore available for overwriting. As opposed to RAM devices in which information is accessed by specifying a particular memory location, once information is stored in a memory location of the CAM, it may be located by comparing every bit in the memory with data placed in a special register known as a compare register. If there is a match of every bit in particular memory locations with every corresponding bit in the register, a Match Flag is asserted to let the user know that the data in the register was found in the CAM device. A priority encoder may sort out which matching memory location has the top priority if there is more than one matching entry, and makes the address of the matching memory location available to the user so that the user may access the matching data. Thus, with a CAM device, the user supplies a piece of data he wants to match to the CAM and get back the address of any matching pieces of data in the CAM.
Known CAM devices are based on typical SRAM or DRAM memory cells that have been modified by the addition of extra transistors that compare the state of the bit stored in each memory cell with the state of a bit of a register. Logically, CAM devices perform an exclusive-NOR finction so that a match is only indicated if both the stored bit and the corresponding register bit have the same state (i.e., "1" or "0"). Generally, CAM devices use a ten transistor memory cell including a six transistor SRAM memory cell and four pull-down NMOS transistors which accomplish the exclusive-NOR functionality and the match line driving. These CAM devices using the ten transistor memory cell may have approximately a 70 to 180 nanosecond (ns) match time and a power dissipation of approximately 0.6 to 1.9 watts. These CAM devices may have sizes which are 256 k and smaller since larger sizes may cause power dissipation problems. These CAM devices as described above, however, have a number of problems, drawbacks and limitations.
One drawback is that known CAM devices have very small storage capacities as compared to other memory devices, such as DRAM devices and SRAM devices. These smaller storage capacities are due to the fact that the AM storage size is principally limited by the large amount of power dissipated by each match line in the CAM. Each match line may have one or more NMOS pull-down transistor associated with it so that for a CAM having 4096 memory locations, a match request causes power dissipation from 4095 match lines transistors since all of the non-matching match lines output low signals, e.g., logic 0. Therefore the associated NMOS pull-down transistors will dissipate power. Another drawback is that attempts to increase the speed performance of conventional CAM devices causes other problems since the faster CAM device leads to increased power dissipation. The problem is that the power dissipation cannot be increased very much without exceeding maximum power dissipation levels. Thus, conventional CAM devices are limited in size and performance because of the power being dissipated by the transistors associated with the match lines.
Another drawback of conventional CAM devices is that the memory devices themselves do not have much built-in intelligence or management functions so that, for each new operation environment, a piece of software must be written which is then responsible for management of the functions of the CAM device. The CAM management functions may include disabling unused CAM memory cells, maintaining a list of available CAM memory cells and checking for and avoiding insertion of duplicate data in more than one CAM memory cell.
Thus, it is desirable to provide a content addressable memory which overcomes the above described drawbacks, problems and limitations of conventional CAM devices and it is to this end that the present invention is directed.